package swardToOffer.struct_4_tree;

import java.util.ArrayDeque;

// 面试题32（二）：分行从上到下打印二叉树
// 题目：从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。
// 由于打印顺序是根->【左子->右子】->【左左子->左右子->右左子->右右子】，所以用前序遍历的方式
// 借用队列将当前节点弹出（打印）的同时加载它的子节点
//
public class PrintTreesInLines {
    void printTreeInLines(TreeNode root){
        if (root==null) return;
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            for (int i = queue.size(); i >0 ; i--) {//这个for循环是分层打印的关键，queue.size保存当前层的节点数量
                TreeNode t = queue.poll();
                System.out.print(t.val+" ");
                if (t.left!=null) queue.offer(t.left);
                if (t.right!=null) queue.offer(t.right);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        PrintTreesInLines Main = new PrintTreesInLines();
        int[] nums = {1,2,3,4,5,6,7,8};
        TreeNode root = TreeUtil.build(nums, 0, 7);
        Main.printTreeInLines(root);
        System.out.println();
        TreeUtil.LevelTraversal(root);
    }
}
